package fpTree;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

import stats.RpTreeTooManyStats;

import mining.CsvReader;
import mining.ItemSetMining;

public class RpTreeTooMany extends ItemSetMining
{
	private final RpTreeTooManyStats stats;
	private final static boolean write = true;
	private BufferedWriter bw;
	
	public static void main(String[] args)
	{
//		RpTreeTooMany rte = new RpTreeTooMany("./datasets/spect/SPECT.all.modified");
//		RpTreeTooMany rte = new RpTreeTooMany("./datasets/connect4/connect-4.data.modified");
		RpTreeTooMany rte = new RpTreeTooMany("./datasets/mock/mock.data.4.modified");
		
		rte.setMinFreqItemsetSupport(5);
		rte.setMinRareItemsetSupport(1);
		rte.run();
		
//		rte.testTree();
	}
	
	
	public RpTreeTooMany(String filePath)
	{
		super(filePath);
		this.stats = new RpTreeTooManyStats();
		this.stats.className = this.getClass().getSimpleName();
		this.stats.write = write;
		this.stats.location = filePath;
		
		if (write) {
			try
			{
				this.bw = new BufferedWriter(new FileWriter(filePath + "." + this.getClass().getSimpleName()));
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}
	}
	
	public void run()
	{
		this.stats.minRareItemsetSup = this.getMinRareItemsetSupport();
		this.stats.minFreqItemsetSup = this.getMinFreqItemsetSupport();
		
		// start timing
		long t1 = System.nanoTime();
		
		ExtNode root = new ExtNode();
		
		Vector<Integer> itemFreqs = this.findDbInfo();

//		System.out.println("itemBelowSupport: " + itemsBelowSupport);
		
		BitSet itemsBelowSupport = new BitSet(itemFreqs.size()); // keep track of items below minSupport
		Map<Integer, Integer> itemFreqsMap = new HashMap<Integer, Integer>();
		for (int item = 0; item < itemFreqs.size(); item++)
		{
			if (itemFreqs.get(item) < this.getMinRareItemsetSupport())
			{
				itemsBelowSupport.set(item);
			} else 
			{
				itemFreqsMap.put(item, itemFreqs.get(item));
			}
		}
		
		List<Integer> fList = new ArrayList<Integer>(itemFreqsMap.keySet());
		Collections.sort(fList, new FListComparator(itemFreqsMap));
		
		Map<Integer, ExtNode> rHeaderTableLast = new HashMap<Integer, ExtNode>();
		Map<Integer, ExtNode> rHeaderTable = new LinkedHashMap<Integer, ExtNode>();
		initialiseLinkedHashMap(rHeaderTable, fList);
		
		final Map<Integer, Integer> fListMap = listToMap(fList);
		Comparator<Integer> comparator = new Comparator<Integer>()
		{
			@Override
			public int compare(Integer s1, Integer s2)
			{
				return fListMap.get(s1) - fListMap.get(s2);
			}
		};
		
		for (CsvReader reader = new CsvReader(this.filePath); reader.hasNext();)
		{
			List<Integer> transaction = new ArrayList<Integer>(reader.readIgnore(itemsBelowSupport));
			
			// sort items in this transaction
			Collections.sort(transaction, comparator);
			
			processTransaction(transaction, 1, root, rHeaderTable, rHeaderTableLast);
		}
		
		root.setCount(this.transactionCount);
//		rareRoot.childrenCount = this.transactionCount;
		if (root.getCount() > this.getMinFreqItemsetSupport())
			root.frequent = true;
		
//		System.out.println(rareRoot.printTree());
//		for (ExtNode node : rareRoot.getChildren().values())
//			System.out.println("ChildExists: " + this.existsInChildrenRecursive(node, 5));

		multiPath(rHeaderTable, Collections.<Integer> emptySet(), root, "");
		this.stats.iterations = this.stats.numIterationItemsets.size();
		
		if (write)
		{
			try
			{
				this.bw.close();
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}
		
		long t2 = System.nanoTime();
		this.stats.runtime = (t2 - t1) / 1000000;
		
		System.out.println(this.stats);
		
	}
	
	// transaction is already sorted...
	private void processTransaction(List<Integer> transaction, int frequency, ExtNode root,
									Map<Integer, ExtNode> rHeaderTable, Map<Integer, ExtNode> rHeaderTableLast)
	{
		int freqSup = this.getMinFreqItemsetSupport();
		
		ExtNode current = root;
		for (int item : transaction)
		{
			// look for the right child to increment, if one exists
			if (current.getChildren().containsKey(item))
			{ // if child exists, increment count
				current.childrenCount += frequency;
				current = (ExtNode) current.getChildren().get(item);
				current.setCount(current.getCount() + frequency);
				
				if (current.getCount() >= freqSup)
					current.frequent = true;
				
			} else
			{ // if it does not, create a child
				ExtNode nn = new ExtNode();
				nn.itemName = item;
				nn.setCount(frequency); // initialise count
				current.getChildren().put(item, nn); // add new node to parent
				nn.parent = current; // add parent to new node
				
				current.childrenCount += frequency; // keep count of number of children
				
				// add node-link
				// headerTable.get(string).add(nn);
				
				// have to test with null and not containsKey because
				// headerTable has been initialised
				if (rHeaderTable.get(item) == null)
				{
					// System.out.println("adding first");
					rHeaderTable.put(item, nn);
				}
				if (!rHeaderTableLast.containsKey(item))
				{
					rHeaderTableLast.put(item, nn);
				} else
				{
					rHeaderTableLast.put(item, nn).setNodeLink(nn);
				}
				
				current = nn;
			}
		}
		
	}
	
	long iterationItemsetCount;
	
	private void multiPath(Map<Integer, ExtNode> headerTable, final Set<Integer> alpha, ExtNode root, String spacing)
	{
		spacing = "@" + spacing + " ";
		
//		System.out.println(spacing + "going to mine items in this order: " + headerTable.keySet());
		for (int itemName : headerTable.keySet())
		{ // for each item in Q... i.e. branching part
		
//			if (this.allNodeLinksFreq(headerTable.get(itemName)))
//				continue;
			
			// DOES NOT WORK - this will only look at first node
			// INSTEAD, have to look through all node links... and if all above freq threshold, skip this item.
			// if none above threshold, mine normally,
			// if some are above threshold... still have to continue - i.e. build conditional tree and mine
				// but in that conditional tree, can ignore all those that have all nodes above threshold - (taken care of by recursion)
			
//			if (itemName == 3 && alpha.isEmpty()) {
//				System.out.println("ahhh");
//			}
			
			if (alpha.isEmpty())
			{
				this.iterationItemsetCount = 0;
			}
			
			final Set<Integer> freqPatternQ = new LinkedHashSet<Integer>(alpha);
			freqPatternQ.add(itemName); // beta = ai UNION alpha (line 10)
			
			ExtNode newRoot = new ExtNode();
			ExtNode firstNodeLink = headerTable.get(itemName);
			Map<Integer, ExtNode> newHeaderTable = constructConditional(firstNodeLink, spacing, newRoot);
			
//			System.out.println("conditional on: " + firstNodeLink.itemName);
//			System.out.println(newRoot.printTree());
			multiPath(newHeaderTable, freqPatternQ, newRoot, spacing);
			
			int tally = tallyNodeLinkCount(firstNodeLink);
			
//			System.out.println(freqPatternQ);
			
			if (tally < this.getMinFreqItemsetSupport())
			{
//				System.out.println("writing: " + freqPatternQ + "-" + tally + " " + getMinFreqItemsetSupport());
				this.iterationItemsetCount++;
				this.stats.numItemsets++;
				this.stats.numItemsetItems += freqPatternQ.size();
				writeToFile(freqPatternQ, tally);
			} else {
//				System.out.println("not writing: " + freqPatternQ + "-" + tally + " " + getMinFreqItemsetSupport());
			}
			
			if (alpha.isEmpty())
			{
//				System.out.println(itemName + " | " + this.iterationItemsetCount);
				this.stats.numIterationItemsets.add(this.iterationItemsetCount);
			}
			
		}
	}

	private int tallyNodeLinkCount(ExtNode node)
	{
		int count = 0;
		for (ExtNode temp = node; temp != null; count += temp.getCount(), temp = temp.getNodeLink())
			;
		return count;
	}
	
	int fileNum;
	private void writeToFile(Set<Integer> itemset, int support)
	{
		if (!write)
			return;
		
		try
		{
			if (this.stats.numItemsets % (1 << 22) == 0)
			{
				this.fileNum++;
				this.bw.close();
				this.bw = new BufferedWriter(new FileWriter(this.filePath + "." + this.getClass().getSimpleName() + "."
						+ this.fileNum));
			}
			this.bw.write(itemset.toString());
			this.bw.write(",");
			this.bw.write(Integer.toString(support));
			this.bw.newLine();
		} catch (IOException e)
		{
			e.printStackTrace();
		}
	}
	
	private Map<Integer, ExtNode> constructConditional(ExtNode firstNode, String spacing, ExtNode root)
	{
		
		// printing node links
//		Node temp = firstNode;
//		StringBuilder sb = new StringBuilder();
//		while (temp != null)
//		{
//			sb.append(temp + " ");
//			temp = temp.nodeLink;
//		}
		
		// build conditional pattern base, and count item frequencies
		Map<List<Integer>, Integer> conditionalPatterns = new HashMap<List<Integer>, Integer>();
		// for storing 1-itemset frequencies
		Map<Integer, Integer> freqs = new HashMap<Integer, Integer>();
		
		ExtNode linkNode;
		for (linkNode = firstNode; linkNode != null; linkNode = linkNode.getNodeLink())
		{
			// skip frequent nodes...
			if (linkNode.frequent)
				continue;
			
			// build pattern by going up parents
			// stores 1 conditional pattern
			ArrayList<Integer> pattern = new ArrayList<Integer>();
			
			// don't include the current node in the header table
			ExtNode node = linkNode.parent;
			
			while (node != null && node.itemName != -1)
			{
				// counting 1-itemset frequencies by going through link
				// nodes and their parents
				if (!freqs.containsKey(node.itemName))
				{
					freqs.put(node.itemName, linkNode.getCount());
				} else
				{
					freqs.put(node.itemName, freqs.get(node.itemName) + linkNode.getCount());
				}
				pattern.add(node.itemName);
				node = node.parent;
			}
			// add pattern to pattern-base
			Collections.reverse(pattern); // have to reverse pattern since the parents were added to the end of the list

			if (!pattern.isEmpty())
				conditionalPatterns.put(pattern, linkNode.getCount());
		}
		
		List<Integer> newFList = createFList(freqs);
		
//		List<Integer> aList = new ArrayList<Integer>();
//		List<Integer> fList = new ArrayList<Integer>();
//		List<Integer> rList = new ArrayList<Integer>();
//		createLists(freqs, aList, fList, rList);
		
		// make tree
		// build the tree using transactions
		if (!conditionalPatterns.isEmpty())
		{
			return processTransactions(conditionalPatterns, newFList, root);
		} else
		{
			return Collections.emptyMap();
		}
	}
	
	private List<Integer> createFList(Map<Integer, Integer> itemFreqs)
	{
		List<Integer> fList = new ArrayList<Integer>();
		
		for (int itemName : itemFreqs.keySet())
		{
			if (itemFreqs.get(itemName) >= this.getMinRareItemsetSupport())
				fList.add(itemName);
		}
		
		Collections.sort(fList, new FListComparator(itemFreqs));
		
		return fList;
	}

	private Map<Integer, ExtNode> processTransactions(Map<List<Integer>, Integer> transactions,
														final List<Integer> fList, ExtNode root)
	{
		// ExtNode root = new ExtNode(); // use the root provided
		
		Map<Integer, ExtNode> headerTable = new LinkedHashMap<Integer, ExtNode>();
		// ensuring the order of iteration will be the reverse order of fList
		initialiseLinkedHashMap(headerTable, fList);
		
		final Map<Integer, Integer> fListMap = listToMap(fList);
		
		// testing
		// ArrayList<Integer> testArray = new ArrayList<Integer>(fList);
		// Collections.reverse(testArray);
		// assert(testArray.equals(new
		// ArrayList<Integer>(headerTable.keySet()))) :
		// "Order is not reversed.";
		
		Map<Integer, ExtNode> headerTableLast = new HashMap<Integer, ExtNode>();
		
		Comparator<Integer> comparator = new Comparator<Integer>()
		{
			@Override
			public int compare(Integer s1, Integer s2)
			{
				return fListMap.get(s1) - fListMap.get(s2);
			}
		};
		
		for (List<Integer> transaction : transactions.keySet())
		{
			
			// this needs to be before sorting...
			int frequency = transactions.get(transaction);
			
			this.removeItemsBelowSupport(transaction, fList);
			
			Collections.sort(transaction, comparator); // sort items in this transaction

			processTransaction(transaction, frequency, root, headerTable, headerTableLast);
		}
		
		return headerTable;
	}

	private void removeItemsBelowSupport(Collection<Integer> transaction, final Collection<Integer> fList)
	{
		for (Iterator<Integer> i = transaction.iterator(); i.hasNext();)
		{
			int s = i.next();
			if (!fList.contains(s))
			{
				i.remove();
			}
		}
	}
	
	private void initialiseLinkedHashMap(Map<Integer, ExtNode> headerTable, List<Integer> fList)
	{
		for (int i = fList.size() - 1; i >= 0; i--)
		{
			headerTable.put(fList.get(i), null);
		}
	}
	
	private Map<Integer, Integer> listToMap(List<Integer> list)
	{
		Map<Integer, Integer> listMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < list.size(); i++)
		{
			listMap.put(list.get(i), i);
		}
		return listMap;
	}
	
}
